package leetcode.editor.vscdev.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/* 77. Combinations
 * https://leetcode.com/problems/combinations/
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * 你可以按 任何顺序 返回答案。
 */

public class lc77 {
    class Solution {
        List<List<Integer>> result= new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        public List<List<Integer>> combine(int n, int k) {
            backtracking(n,k,1);
            return result;
        }
        // 注意右边界是可以取到的
        public void backtracking(int n,int k,int startIndex){
            if (path.size()>=k){
                // 当长度等于上限,添加当前路径到结果
                // !!注意不要直接把path添加到res,后续对该path空间操作会产生影响
                result.add(new ArrayList<>(path));
                return;
            }
            for (int i = startIndex; i < n; i++){
                // 加入路径
                path.add(i);
                // 递归深入
                backtracking(n, k, i+1);
                // 回溯出来,除去路径
                path.removeLast();
            }
        }
    }
}
